package Search;
/**
 * LGSearch is used to perform a pattern match on a directed labelled graph
 * @author Darren
 */
import java.util.Vector;
import java.util.ArrayList;

import Common.Graph;
import Common.Pattern;

public class LGSearchRegExp {

	private Pattern pattern;
	private Graph graph;
	String[] searchPattern;
	/**
	 * Constructor for LGSearch
	 *
	 * @param p the pattern to find
	 * @param g the graph to find the pattern within
	 */
	public LGSearchRegExp(Pattern p, Graph g) {
		pattern = p;
		graph = g;
	}

	/**
	 * Traverse the graph looking for the symbols in the pattern in the order
	 * they appear in the pattern
	 *
	 * @param g a 2D representation of the graph
	 * @param numVertices the number of vertices in the graph
	 * @param curNode the index of the vertex to look from
	 * @param patternIndex the index of the symbol in the pattern to find
	 * @param seq the sequence of nodes to visit to traverse the graph in pattern order
	 * @param seqLen the length of the sequence, used for determining when the sequence has been found
	 */
	public void findOrderedPatternSymbols(int[][] g, int numVertices, int curNode, int patternIndex, int seq[], int seqLen) {

		// Have we found every symbol in the pattern
		if (patternIndex < seqLen) {

			// While the sequence has not been found
			// For every node adjacent to the current node is it's label equal to the next symbol in the pattern
			for (int adjNode = 0; adjNode < numVertices && seq[seqLen -1] == -1; adjNode++) {

				// Is the current node adjacent to this node
				if (g[curNode][adjNode] == 1) {

					// Does this node have the label we are looking for
					if (this.graph.getLabelAt(adjNode).equals(this.searchPattern[patternIndex])) {

						// Update the sequence of nodes to traverse
						seq[patternIndex] = adjNode;
						// Recursively look for a node that has the next label in the pattern from the adjacent node
						findOrderedPatternSymbols(g, numVertices, adjNode, patternIndex+1, seq, seqLen);
					}
				}
			}
		}
	}

	/**
	 * Find this iteration's search pattern
	 *
	 * @param the value of this iteration
	 * @return the ith search pattern
	 */
	private String[] findSearchPattern(int i) {
		int seqLen = this.pattern.length() + i * this.pattern.optLength();
		String[] searchPattern = new String[seqLen];
		int optGrpCnt = 0;
		int index = 0;
		for (int j = 0; j < this.pattern.lengthWithMarkers(); j++) {
			if (this.pattern.elementAtWithMarkers(j).equals("*")) {
				for (int k = 0; k < i; k++) {
					Vector<String> optSymbolGroup = this.pattern.getOptSymbolGroup(optGrpCnt);
					for (int l = 0; l < optSymbolGroup.size(); l++) {
						searchPattern[index] = optSymbolGroup.elementAt(l);
						index++;
					}
				}
				optGrpCnt++;
			}
			else {
				searchPattern[index] = this.pattern.elementAtWithMarkers(j);
				index++;
			}
		}
		return searchPattern;
	}

    /**
     * Search the graph for the given pattern described by a regular expression
     *
     * @return one sequence that satisfies the regular expression
     */
	public int[] Search() {

		boolean seqFound = false;
		// The sequence of nodes to traverse
		int[] sequence = new int[1];
		// The number of regular expression expansions to make before aborting
		int numExpansionsRegExp = 10;
		// Keep expand the regular expression while the sequence has not been found
		for (int i = 0; i < numExpansionsRegExp && !seqFound; i++ ) {
			this.searchPattern = findSearchPattern(i);

			// Find a list of nodes that have the first symbol in the pattern
			ArrayList<Integer> nodes = this.graph.getIndexOf(this.searchPattern[0]);

			// The sequence of nodes to traverse is equal in length to the pattern
			int seqLen = this.searchPattern.length;
			sequence = new int[seqLen];

			// Create a 2D representation of the graph for searching
			int[][] g = graph.getEdgeMatrix();
			int numVertices = graph.getNumberOfVertices();

			// Loop through the nodes that have the first symbol in the pattern
			for (int j = 0; j < nodes.size() && !seqFound; j++) {
				int startVertex = nodes.get(j);
				// The index in the pattern to look from
				int patternIndex = 0;
				// The sequence of nodes in the graph to traverse
				int[] seq = new int[seqLen];
				seq[patternIndex] = startVertex;
				// The remainder of the sequence is unknown
				for (int k = 1; k < seqLen; k++) {
					seq[k] = -1;
				}
				// Can all the symbols in the pattern be reached from this node in the correct order
				findOrderedPatternSymbols(g, numVertices, startVertex, patternIndex+1, seq, seqLen);

				// Check for success when a node whose label is equal to the last symbol in the patter is visited
				if (seq[seqLen -1] != -1){
					seqFound = true;
					sequence = seq;
				}
			}
		}
		// Check for failure
		if (!seqFound) {
			sequence[0] = -1;
		}
		return sequence;
	}
}